#!/usr/bin/env ruby
=begin
Equipe:
  Átila Camurça Alves
  Magno Barroso Albuquerque

Ciência da Compatação 2010.01 manhã

Implementação do Algoritmo RSA de criptografia e descriptografia.

use Ruby 1.8.7
=end

class AlgorithmRSA
  attr_accessor :v_letters, :v_encript, :v_decript

  def initialize
    @v_letters = Array.new
    set_upcase
    set_downcase
    @v_encript = Array.new
    @v_decript = Array.new
    self
  end

=begin
Author  : atila camurca
Date    : 15/05/2010
Version : 1.0
Return  : #self
Description
  Preenche o #Array *v_letters* com as letras minúsculas e o espaço.
=end
  def set_downcase
    str = "abcdefghijklmnopqrstuvwxyz "
    for i in (0...str.size)
      @v_letters.push(str[i,1])
    end
    self
  end

=begin
Author  : atila camurca
Date    : 15/05/2010
Version : 1.0
Return  : #self
Description
  Preenche o #Array *v_letters* com as letras maiúsculas.
=end
  def set_upcase
    str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    for i in (0...str.size)
      @v_letters.push(str[i,1])
    end
    self
  end

=begin
Author  : atila camurca
Date    : 15/05/2010
Version : 1.0
Return  : #Integer
Description
   Retorna o máximo divisor comum entre dois números.
Parameters
  e #Integer : o valor de _e_
  z #Integer : o valor de _z_
=end
  def mdc e, z
    great = 0
    aux = 0;
    if e > z
      until e % z == 0
        aux = e % z
        e = z
        z = aux
      end
      great = z
    else
      until z % e == 0
        aux = z % e
        z = e
        e = aux
      end
      great = e
    end
    return great
  end

=begin
Author  : atila camurca
Date    : 15/05/2010
Version : 1.0
Return  : #Integer
Description
   Encontra o valor de _e_ para ser utilizado no algoritmo RSA.
Parameters
  z #Integer : o valor de _z_
  p #Integer : um número primo _p_
  q #Integer : um número primo _q_
=end
  def find_e z, p, q
    great = 0
    e = 2 # suposição
    until great == 1
      e = e + 1
      great = mdc(e, z)
      z = (p - 1) * (q - 1)
    end
    return e
  end

=begin
Author  : atila camurca
Date    : 15/05/2010
Version : 1.0
Return  : #Integer
Description
   Algoritmo de Euclides.
   Encontra o valor para a variável _d_.
Parameters
  e #Integer : o valor de _e_
  z #Integer : o valor de _z_
=end
  def euclides_extended e, z
    u1 = 1; u2 = 0; u3 = z
    v1 = 0; v2 = 1; v3 = e

    until v3 == 0
      q = (u3/v3)
      t1 = u1 - q * v1
      t2 = u2 - q * v2
      t3 = u3 - q * v3

      u1 = v1; u2 = v2; u3 = v3

      v1 = t1; v2 = t2; v3 = t3
    end
    
    if u2 < 0
      return u2 + z
    else
      return u2
    end
  end
  
=begin
Author  : atila camurca, magno barroso
Date    : 16/05/2010
Version : 1.0
Return  : #String
Description
   Recebe uma mensagem e retorna a mensagem criptografada.
=end
  def encript_message msg, e, n
    #v_encript = Array.new
    # percorre a palavra e faz a letra _m_ elevado e _e_ modulo _n_
    @v_encript.clear
    for i in (0...msg.size)
      letter = get_letter(msg[i,1])
      @v_encript.push( ((letter + 1) ** e) % n )
    end

    # converte os valores encontrados em outra letra
    # fazer essa parte em metodo externo. Pois é necessário guardar o valor original do vetor em inteiro.
    v_letter = rsa2letter(@v_encript)
    return v_letter.join
  end

=begin
Author  : atila camurca
Date    : 16/05/2010
Version : 1.0
Return  : #String
Description
   Descriptografa uma mensagem previamente carregada pela chamada do método AlgorithmRSA#encript_message.
   Antes de chamar o método, certifique-se de ter chamado o AlgorithmRSA#encript_message.
   Caso contrário o programa é encerrado.
=end
  def decript_message d, n
    if @v_encript.empty?
      puts "É necessário primeiro criptografar a palavra."
      exit 1
    end

    # percorre a palavra criptografada e faz a letra _c_ elevado a _d_ modulo _n_
    for i in (0...@v_encript.size)
      @v_decript.push( ((@v_encript[i]) ** d) % n )
    end

    v_letter = rsa2letter(@v_decript)
    return v_letter.join
  end

=begin
Author  : atila camurca
Date    : 15/05/2010
Version : 1.0
Return  : #Array #String
Description
   Converte um #Array de números em suas letras correspondentes.
Parameter
   v_rsa #Array : vetor de números a ser convertidos.
=end
  def rsa2letter v_rsa
    v_letter = Array.new
    for j in (0...v_rsa.size)
      v_letter.push(get_letter_index(v_rsa[j]))
    end
    return v_letter
  end

=begin
Author  : atila camurca
Date    : 15/05/2010
Version : 1.0
Return  : #String
Description
   Faz a busca de uma determinada letra através de seu índice.
Parameter
   value_i #Integer : valor do índice da letra.
=end
  def get_letter_index value_i
    while value_i > 53 or value_i < 0
      value_i = value_i - 53 if value_i > 53
      value_i = value_i + 53 if value_i < 0
    end

    return @v_letters.at(value_i - 1)
  end

=begin
Author  : atila camurca
Date    : 15/05/2010
Version : 1.0
Return  : #Integer
Description
   Retorna o índice da letra no vetor de letras.
Parameter
   value_s #String : letra que se deseja encontrar o índice.
=end
  def get_letter value_s
    return @v_letters.index(value_s)
  end
  
=begin
Author  : magno barroso
Date    : 15/05/2010
Version : 1.0
Return  : #Boolean
Description
   Verifica se um número é primo e retorna #true se for primo, #false caso contrário.
Parameter
   num #Integer : número a ser verificado
=end
  def primo? num
    count = 0
    for i in (2...num)
      if num % i == 0
        count = count + 1
      end
    end
    if count > 0
      puts "#{num} não é um número primo. Digite outro: "
      print "ruby@rsa> "
      return false
    else
      return true
    end
  end
end

########
# MAIN #
########
begin
  puts "\t~ Algoritmo RSA ~"
  puts "\nDesenvolvedores:"
  puts "   > Átila Camurça Alves\n   > Magno Barroso Albuquerque\n\n"
  puts "Para criptografar sua frase é necessário dois números primos."
  # variáveis para o programa
  p = 0; q = 0; rsa = AlgorithmRSA.new

  puts "Digite o primeiro número primo:"
  print "ruby@rsa> "
  # enquanto não for um número primo, repita o bloco.
  begin
    num1 = gets.to_i
    if num1 == 0
      puts "Programa encerrado."
      exit 1
    end
  end until rsa.primo?(num1)
  p = num1
  puts "\n"

  puts "Digite o segundo número primo:"
  print "ruby@rsa> "
  # enquanto não for um número primo, repita o bloco.
  begin
    num2 = gets.to_i
    if num2 == 0
      puts "Programa encerrado."
      exit 1
    end

    # previne que o primeiro número seja igual ao segundo.
    if num1 == num2
      puts "O segundo número deve ser diferente do primeiro. Digite novamente:"
      print "ruby@rsa> "
      redo
    end
  end until rsa.primo?(num2)
  q = num2
  puts "\n"

  # variáveis para o programa
  n = p * q
  z = (p - 1) * (q - 1)
  e = rsa.find_e(z, p, q)
  d = rsa.euclides_extended(e, z)

  puts "Digite a frase a criptografar: [a-z A-Z]"
  print "ruby@rsa> "
  frase = gets
  if frase[0,1] == "0"
    puts "Programa encerrado."
    exit 1
  end
  puts "\n"
  
  enc_msg = rsa.encript_message(frase.chop, e, n)
  puts "Mensagem criptografada: #{enc_msg}"

  desc_msg = rsa.decript_message(d, n)
  puts "\n", "Mensagem descriptografada: #{desc_msg}"
  puts "\n", "Distributed under Copyleft. Share it, Use it and Enjoy it.", "\n"
rescue Exception => ex
  puts "Um erro inesperado ocorreu: ", ex, "\n"
  exit 1
end
